package com.zhn;

/**
 * 给你一棵二叉树的根节点，返回该树的 直径 。
 *
 * 二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
 *
 * 两节点之间路径的 长度 由它们之间边数表示。
 */
public class DiameterOfBinaryTree {
    int res = 0;
    public int dfs(TreeNode root){
        if(root == null){
            return 0;
        }
        //后序遍历
        int l = dfs(root.left);
        int r = dfs(root.right);
        //将这一层的最长左侧和右侧树和上一层遍历的最大结果比较，获取最大长度
        res = Math.max(res,l + r);
        //因为是从下向上查找，最后都需要加上根节点的长度
        //比较左右长度，返回最长的长度
        return Math.max(l,r) + 1;
    }
    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return res;
    }
}
